package heap;

import java.util.*;

/**
 * @author pengfei.hpf
 * @date 2020/2/28
 * @verdion 1.0.0
 */
public class NthUglyNumber {
    public int nthUglyNumber(int n) {

        if(n == 0){
            return 0;
        }
        int[] res = new int[n];
        int i2 = 0;
        int i3 = 0;
        int i5 = 0;
        res[0] = 1;
        for(int i = 1; i < n; i ++){
            int n2 = res[i2] * 2;
            int n3 = res[i3] * 3;
            int n5 = res[i5] * 5;
            int u = Math.min(Math.min(n2,n3), n5);
            if(u == n2){
                i2 ++;
            }
            if(u == n3){
                i3 ++;
            }
            if(u == n5){
                i5 ++;
            }

            res[i] = u;
        }
        return res[n - 1];
    }

    public static void main(String[] args){
        NthUglyNumber ug = new NthUglyNumber();
        System.out.println(ug.nthUglyNumber(2));
    }
}
